#include "PageCache.h"

PageCache PageCache::_pageCache;

PageCache* PageCache::GetInstance()
{
    return &_pageCache;
}
std::mutex& PageCache::GetMtx()
{
    return _mtx;
}

// 返回k页的span
Span* PageCache::NewSpan(size_t k)
{
    if (k >= page_num) // 大于128页
    {
        void* ptr = SystemAlloc(k);
        Span* span = new Span;
        span->_id = (PageID)ptr >> page_shift;
        span->_nPage = k;
        span->_objSize = k << page_shift;
        // 大内存直接使用没有划分，只要第一个pageid，方便回收时查找span
        //_idSpanMap[span->_id] = span;
        _idSpanMap.set(span->_id, span);
        return span;
    }

    // k位置有span
    if (!_spanLists[k].Empty())
    {
        Span* span = _spanLists[k].PopFront();
        // k位置没有span
        if (_spanLists[k].Empty()) _nonEmptyK.erase(k);
        // 分给cc的需要每页映射
        for (PageID id = span->_id; id < span->_id + span->_nPage; id++)
            //_idSpanMap[id] = span;
            _idSpanMap.set(id, span);

        return span;
    }

    // k位置没有span，但k之后的位置有
    auto it = _nonEmptyK.lower_bound(k + 1); //  查找大于等于k+1的元素
    if (it != _nonEmptyK.end())
    {
        Span* span = _spanLists[*it].PopFront(); //*it页的span
        if (_spanLists[*it].Empty())
            _nonEmptyK.erase(*it); // 变空则移除

        Span* kSpan = new Span; // k span
        kSpan->_id = span->_id;
        kSpan->_nPage = k;

        span->_id += k; // 拆分span
        span->_nPage -= k;
        _spanLists[span->_nPage].PushFront(span); // 将span增加到spanlists
        _nonEmptyK.insert(span->_nPage); // 拆分后span的页数

        // 将拆分后的span和kspan记录到idspanmap
        // 分给cc的kspan每一页都需要记录，因为需要通过内存块地址找对应管理的span
        for (PageID id = kSpan->_id; id < kSpan->_id + kSpan->_nPage; id++)
            //_idSpanMap[id] = kSpan;
            _idSpanMap.set(id, kSpan);

        // span只需要记录左右边界就行，用于合并span
        //_idSpanMap[span->_id] = span;
        //_idSpanMap[span->_id + span->_nPage - 1] = span;
        _idSpanMap.set(span->_id, span);
        _idSpanMap.set(span->_id + span->_nPage - 1, span);

        return kSpan;
    }

    // k位置之后没有span
    void* ptr = SystemAlloc(page_num - 1); // 向系统申请128页的内存挂载到span
    Span* span = new Span;

    span->_id = (PageID)ptr >> page_shift;
    span->_nPage = page_num - 1;
    _spanLists[span->_nPage].PushFront(span); // 更新
    _nonEmptyK.insert(page_num - 1); // 更新nonemptyk

    return NewSpan(k); // 代码复用
}

// 查找对应的span
//Span* PageCache::MapObjectToSpan(void* obj)
//{
//    // uorded_map不是线程安全的，查的时候可能其他线程修改了
//    std::unique_lock<std::mutex> lock(_mtx);
//    PageID id = (PageID)obj >> page_shift;
//    auto it = _idSpanMap.find(id);
//    return it != _idSpanMap.end() ? it->second : nullptr;
//}

//unordered_map\map不是线程安全的，map底层红黑树，遍历时其他线程修改发生旋转，原有映射关系变化
//unordered_map底层哈希桶
//使用基数树，减少锁使用，提高效率
Span* PageCache::MapObjectToSpan(void* obj)
{
    PageID id = (PageID)obj >> page_shift;
    Span* span = (Span*)_idSpanMap.get(id);
    assert(span);
    return span;
}

// 将cc中的span返回给pc
void PageCache::ReleaseSpanToPageCache(Span* span)
{
    assert(span);
    // 如果span中的页数超过128，直接回收内存
    if (span->_nPage >= page_num)
    {
        void* ptr = (void*)(span->_id << page_shift);
        SystemFree(ptr);
        delete span;
        return;
    }
    // 向左合并span
    for (;;)
    {
        PageID leftId = span->_id - 1;
        ////
        //auto it = _idSpanMap.find(leftId);
        //if (it == _idSpanMap.end() || it->second->_useCount != 0) break; // 左边没有 或者usecount不等于0
        //Span* leftSpan = it->second;

        Span* leftSpan = (Span*)_idSpanMap.get(leftId);
        if (!leftSpan || leftSpan->_useCount != 0) break; // 左边没有 或者usecount不等于0
        
        if (leftSpan->_nPage + span->_nPage >= page_num) break; //超过128页

        // 合并前从_spnlsts删除leftSpan, span从cc来的，不存在_spanlists中
        _spanLists[leftSpan->_nPage].Erase(leftSpan);
        // k页是否存在span
        if (_spanLists[leftSpan->_nPage].Empty()) _nonEmptyK.erase(leftSpan->_nPage);

        span->_id = leftSpan->_id;
        span->_nPage += leftSpan->_nPage;

        delete leftSpan;
    }
    // 向右合并
    for (;;)
    {
        PageID rightId = span->_id + span->_nPage;
        ////
        //auto it = _idSpanMap.find(rightId);
        //if (it == _idSpanMap.end() || it->second->_useCount != 0) break;
        //Span* rightSpan = it->second;

        Span* rightSpan = (Span*)_idSpanMap.get(rightId);
        if (!rightSpan || rightSpan->_useCount != 0) break;

        if (rightSpan->_nPage + span->_nPage >= page_num) break;

        _spanLists[rightSpan->_nPage].Erase(rightSpan);
        if (_spanLists[rightSpan->_nPage].Empty()) _nonEmptyK.erase(rightSpan->_nPage);

        span->_nPage += rightSpan->_nPage;

        delete rightSpan;
    }

    _spanLists[span->_nPage].PushFront(span);
    // 将span的两端记录，用于后续合并
    //_idSpanMap[span->_id] = span;
    //_idSpanMap[span->_id + span->_nPage - 1] = span;
    _idSpanMap.set(span->_id, span);
    _idSpanMap.set(span->_id + span->_nPage - 1, span);
}